from typing import List

inf = float('inf')


class Solution:
    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        m = len(matrix[0])
        # n行m列
        prefix = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + matrix[i - 1][j - 1]
        # 若n>>m
        # 枚举左右边界
        result = -inf
        for x1 in range(n):
            for x2 in range(x1, n):
                for y1 in range(m):
                    for y2 in range(y1, m):
                        prefix_sums = prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1]
                        if prefix_sums <= k:
                            result = max(result, prefix_sums)
        return result
